package com.cdream.basic.algorithm.leetcode.string;

/**
 * @author cdream
 * @date 6/27/21
 */
public class Question5799 {
    public static void main(String[] args) {
        new Question5799().wonderfulSubstrings("aab");
    }
    public long wonderfulSubstrings(String word) {
        int n = word.length();
        int[] dp =new int[n];
        dp[0] = 1;
        for(int i = 1;i<n;i++){
            int count = 0;
            for(int j = 0;j<=i;j++){
                String s = word.substring(j,i+1);
                if(isBeatifulWord(s)){
                    count++;
                }
            }
            dp[i] = dp[i-1]+count;
        }
        return dp[n-1];

    }

    boolean isBeatifulWord(String s){
        int[] res = new int[10];
        char[] arr = s.toCharArray();
        for(char c : arr){
            res[c-'a']++;
        }
        int count =0;
        for(int i : res){
            if(i%2==1){
                count++;
            }
        }
        return count<2;
    }
}
